Phép chèn và tính cân bằng AVL

Giả sử có một cây tìm kiếm nhị phân cân bằng AVL và u là một nút của T và một nút mới v được chèn vào u. Do v chỉ có thể được chèn vào đúng một trong hai cây con của u nên nhiều nhất là v có thể làm tăng chiều cao của một trong hai cây con đó. Nếu v không làm tăng chiều cao của cây con nàohoặc v làm tăng chiều cao của một cây con nhưng trước đó cây con này có chiều cao nhỏ hơn hoặc bằng chiều cao của cây con kia thì tính cân bằng AVL tại đỉnh u vẫn giữ nguyên. Tính cân bằng AVL tại u chỉ có thể bị phá vỡ khi v làm tăng chiều cao của cây con có chiều cao lớn hơn trong hai cây con của u.

Cũng như vậy, nếu v không làm tăng chiều cao của chính u thì v không làm thay đổi hệ số cân bằng tại các đỉnh tiền bối của u.

Mặt khác, nút v luôn được thêm vào với tư cách là con của một nút trước đó là lá hoặc nửa lá.

Nếu đỉnh cha của v trước khi thêm v là nửa lá, thì chiều cao của cây con gốc cha của v không thay đổi sau khi thêm v còn hệ số cân bằng tại đỉnh cha này bằng 0. Khi đó tất cả các nút tiền bối của cha của v không thay đổi hệ số cân bằng. Tính cân bằng AVL được giữ vững trên toàn bộ cây T.

Nếu đỉnh cha của v trước khi thêm v là lá, gọi u là đỉnh tiền bối của v có mức cao nhất mà tính cân bằng AVL bị phá vỡ.

Như vậy bốn trường hợp sau có thể phá vỡ tính cân bằng AVL tại u

1. Trước khi chèn cây con gốc u lệch trái và v làm tăng chiều cao của cây con trái.
   1. .Sau khi chèn cây con trái lệch trái (Case LL);
   2. .Sau khi chèn cây con trái lệch phải (Case LR).
2. .Trước khi chèn cây con gốc u lệch phải và v làm tăng chiều cao của cây con phải.
   1. .Sau khi chèn cây con phải lệch phải (Case RR);
   2. .Sau khi chèn cây con phải lệch trái. (Case RL)

Tái cân bằng sau phép chèn

Khi tính cân bằng AVL tại u bị phá vỡ, cần một hoặc hai phép quay để tái cân bằng AVL cây con gốc u và biến đổi cây T trở thành cân bằng AVL.

Trường hợp 1 (LL)

Thực hiện phép quay phải tại u.

Trường hợp 2 (LR)

Trước hết thực hiện phép quay trái tại u.left để đưa về TH1 (LL) sau đó thực hiện phép quay phải tại u.

Trường hợp 3 (RR)

Thực hiện phép quay trái tại u.

Trường hợp 4 (RL)

Trước hết thực hiện phép quay phải tại u.right để đưa về TH3 (RR) sau đó thực hiện phép quay trái tại u.

Mã giả

Trong đoạn giả mã sau, height(u) là chiều cao của cây con của u. Khi đỉnh u là lá, height(u)=1. Với mỗi đỉnh u không là lá height(u)=max{height(u.left),height(u.right)}+1. Có thể dùng một phép duyệt hậu thứ tự để tính hàm height(u) tại mọi đỉnh trên cây T. Tuy nhiên, khi mỗi đỉnh mới được chèn vào cây (luôn là lá) ta sẽ tính lại giá trị hàm height(v) với mọi v là tiền bối của đỉnh đó.

 CALCULATE-BALANCE(u) // Tính hệ số cân bằng và chiều cao cây con tại đỉnh u. if  u.right = Null and u.left=Null then     begin         height(u)=1;         balance(u)=0     end;  else     if u.right = Null and u.left<>Null then          begin             height(u)=height(u.left)+1;             balance(u)=height(u)         end     else           if u.left = Null and u.right<>Null then              begin                 height(u)=height(u.right)+1;                 balance(u)=-height(u)             end;         else             begin                 height(u)=max(height(u.left),height(u.right))+1;                 balance(u)=height(u.left)-height(u.right);             end;

 REBALANCE(v)  // Thủ tục này tái cân bằng AVL (nếu bị mất cân bằng) các một đỉnh tiền bối của v bị mất cân bằng AVL.   // Sau đó các  bậc tiền  bối trên nữa sẽ không thay đổi hệ số cân bằng so với trước khi đỉnh v được chèn vào.     // v là lá   //Tìm đỉnh tiền bối v sao cho v có tri số tuyệt đối của v    u= v  while u<> T.root and abs(balance(u)) ≤1 do       begin           CALCULATE-BALACE(u)          u=u.parent;      end;     if balance(u)>2 then       if balance(u.left)>0 then          RIGHT-ROTATE(u)      else          begin              LEFT-ROTATE(u.left);              RIGHT-ROTATE(u);          end;  else      if balance(u)<-2 then          if balance(u.right)< 0 then              LEFT-ROTATE(u)          else              begin                  RIGHT-ROTATE(u.right);                  LEFT-ROTATE(u);              end;